#include <stdlib.h>
#include <stdio.h>
#include "count_inversion.h"
#include "common/common.h"
#include "common/array.h"

static int merge_count_inversion_result(int array[], int mid, int len) {
  int count = 0;
  int *sub_array1, *sub_array2;
  int i, j, n;

  sub_array1 = (int*)malloc(mid * sizeof(int));
  sub_array2 = (int*)malloc((len - mid) * sizeof(int));
  for (i = 0; i < mid; ++i) {
    sub_array1[i] = array[i];
  }
  for (j = 0; i < len; ++j, ++i) {
    sub_array2[j] = array[i];
  }
  count = 0;
  for (i = 0, j = 0, n = 0; i < mid && j < len - mid; ) {
    if (sub_array1[i] > sub_array2[j]) {
      array[n++] = sub_array2[j];
      count += mid - i;
      ++j;
    } else {
      array[n++] = sub_array1[i];
      ++i;
    }
  }
  while (i < mid) {
    array[n++] = sub_array1[i++];
  }
  while (j < len - mid) {
    array[n++] = sub_array2[j++];
  }
  free(sub_array1);
  free(sub_array2);
  return count;
}

static int count_inversion_impl(int array[], int len) {
  if (len > 1) {
    int mid = len / 2;
    int count = count_inversion_impl(&array[0], mid);
    count += count_inversion_impl(&array[mid], len - mid);
    return count + merge_count_inversion_result(array, mid, len);
  } else {
    return 0;
  }
}

int count_inversion(array_t *array) {
  return count_inversion_impl(array->data, array->size);
}
